package optimization;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.*;

import temp.Temp;
import util.List;
import assem.Instr;
import flow_graph.AssemFlowGraph;
import graph.Node;

public class ReachingDefinition {

	private AssemFlowGraph cfg;

	private Map<Node, Set<Node>> in;
	private Map<Node, Set<Node>> out;
	private Map<Node, Set<Node>> gen;
	private Map<Node, Set<Node>> kill;

	/* defs(t) é o conjunto de nós que definem o temporário t */
	private Map<Temp, Set<Node>> defs;

	public Set<Node> getIn(Node n){
		return in.get(n);
	}

	public Set<Node> getOut(Node n){
		return out.get(n);
	}

	public Set<Node> getKill(Node n){
		return kill.get(n);
	}
	
	public Set<Node> getDefs(Temp temp)
    {
        return defs.get(temp);
    }

	
	public ReachingDefinition(List<Instr> l, AssemFlowGraph cfg) {
		
		this.cfg = cfg;
		populateGen();
		populateKill();
		populateInOut();
		
	}

	/*
	 * Método que popula o HashMap 'gen', com base na instrução referente ao nó.
	 * Caso a instrução defina algum registrador, o nó é adicionado ao HashMap cuja chave é o próprio nó.
	 * Além disso, este método popula o HashMap 'defs', com base nos registradores que a instrução define.
	 */
	private void populateGen(){
		
		gen = new HashMap<Node, Set<Node>>();
		defs = new HashMap<Temp, Set<Node>>();
		Instr instGen;
		Node nodeGen;
		
		Iterator<Node> nodesGen = cfg.nodes().iterator();
		while(nodesGen.hasNext()){
			
			nodeGen = nodesGen.next();
			HashSet<Node> n = new HashSet<Node>();
			instGen = cfg.getInstr(nodeGen); 
			// Verifica se a instrução referente ao nó define alguma coisa
			if(instGen.def() != (null) && instGen.def().size() > 0){
				n.add(nodeGen);
				Iterator<Temp> tempDefs = cfg.getDefined(nodeGen).iterator();
				while(tempDefs.hasNext()){
					Temp tempDef = tempDefs.next();
					// Caso 'defs' já possua o temporário, simplesmente adiciona o nó atual ao set de nós referente a este temporário.
					if(defs.containsKey(tempDef)){
						defs.get(tempDef).add(nodeGen);
					} else {
						// Caso contrário, adicionamos o temporário a 'defs' e também adicionamos o nó atual ao set referente ao temporário.
						HashSet<Node> nodeDefs = new HashSet<Node>();
						nodeDefs.add(nodeGen);
						defs.put(tempDef, nodeDefs);
					}
				}
			}
			// Ao final, adicionamos o nó da iteração e seu respectivo HashSet ao HashMap 'gen'.
			gen.put(nodeGen, n);
			
		}
		
	}
	
	/*
	 * Método que popula o HashMap 'kill', com base na instrução referente ao nó.
	 * Caso a instrução defina algum registrador, verificamos os outros nós onde ele também é definido, pois
	 * a definição no nó atual irá 'matar' todas as outras definições.
	 */
	private void populateKill(){
		
		kill = new HashMap<Node, Set<Node>>();
		Instr instKill;
		
		List<Node> nodes = cfg.nodes();
		Iterator<Node> iter = nodes.iterator();
		while(iter.hasNext()){
			Node node = (Node) iter.next();
			HashSet<Node> hashset = new HashSet<Node>();
			instKill = cfg.getInstr(node);

			//Verifica se a instrução faz alguma definição
			if (instKill.def() != null && instKill.def().size() > 0) {
				
				//Acha os temporários definidos no nó node
				List<Temp> aux = cfg.getDefined(node);
				Iterator<Temp> iter2 = aux.iterator();
				while(iter2.hasNext()){
					Temp temp = (Temp) iter2.next();

					//Acha o set de nós definidos no nó node
					Set<Node> s_nodes = defs.get(temp);

					Iterator iter3 = s_nodes.iterator();
					while(iter3.hasNext()){
						Node n = (Node) iter3.next();
						if(!gen.get(node).contains(n))
							hashset.add(n);
					}
				}
				
			}
			
			kill.put(node,hashset);		
			
		}
	}
	
	private void populateInOut(){
		
		// Inicializamos in e out como vazios inicialmente.
		in = new HashMap<Node, Set<Node>>();
		out = new HashMap<Node, Set<Node>>();
		
		
		
		// (1) para cada instrucao I, fazer out[I] = gen[I]]
		Iterator<Node> nodesInOut = cfg.nodes().iterator();
		while(nodesInOut.hasNext()){
			Node nodeInOut = nodesInOut.next();
			HashSet<Node> inHash = new HashSet<Node>();
			HashSet<Node> outHash = new HashSet<Node>();

			// criamos os HashSets 'in' inicialmente vazios
			in.put(nodeInOut, inHash);
			// Se existe 'gen' para o nó nodeInOut, adicionamos o mesmo ao HashSet outHash.
			if(gen.get(nodeInOut) != null){
				outHash = new HashSet<Node>(gen.get(nodeInOut));
			}
			// criamos os HashSets 'out' populados com 'gen' ou, caso este seja nulo, criamos com um HashSet vazio.
			out.put(nodeInOut, outHash);	
		}
		
		// Utilizamos dois Set<Node> para verificar se o in ou o out mudaram a cada iteração. Caso não tenha havido mudança, o algoritmo pára.
		Set<Node> in_changed = new HashSet<Node>();
		Set<Node> out_changed = new HashSet<Node>();
		
		int change = 1; /* to get the while-loop going */
		// Iteração que popula 'in' e 'out'. Paramos quando nenhum dos Sets é atualizado ao final de uma iteração.
		while(change == 1){
			Iterator<Node> nodesFixPtIter = cfg.nodes().iterator();
			while(nodesFixPtIter.hasNext()){
				Node nodeFixPtIter = nodesFixPtIter.next();
				// Atualizamos in_clear e out_clear
				in_changed.clear();
				in_changed.addAll(in.get(nodeFixPtIter));
				out_changed.clear();
				out_changed.addAll(out.get(nodeFixPtIter));
				
				// Atualizamos o valor de 'in' com os valores de 'out' de todos os seus predecessores.
				Iterator<Node> inPreds = nodeFixPtIter.getPreds().iterator();
				while(inPreds.hasNext()){
					Node inPred = inPreds.next();
					in.get(nodeFixPtIter).addAll(out.get(inPred));	
				}
				
				// HashSet auxiliar para calcular (in - kill)
				Set<Node> inMinusKill = new HashSet<Node>();
				inMinusKill.addAll(in.get(nodeFixPtIter));
				inMinusKill.removeAll(kill.get(nodeFixPtIter));
				
				// Como 'out' já possui o valor de 'gen', simplesmente realizamos a união de 'out' com 'inMinusKill'.
				out.get(nodeFixPtIter).addAll(inMinusKill);
				
				// Caso ambos os sets 'in' e 'out' sejam iguais, a iteração pára.
				if (in_changed.containsAll(in.get(nodeFixPtIter)) && out_changed.containsAll(out.get(nodeFixPtIter))){
					change = 0;
				}	
			}	
		}
	}
	
	
}
